package com.xcf.leetcode;

import javax.xml.bind.SchemaOutputResolver;
import java.util.HashSet;
import java.util.Set;

/**
 * LongestSubstring <br>
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 * @author xiaocf <br>
 * @version 1.0 <br>
 * @date 2020/7/9 9:45 <br>
 */
public class LongestSubstring {

    /**
     * 暴力解法
     */
    public int lengthOfLongestSubstring(String s) {
        if (null == s || "".equals(s)) {
            return 0;
        }
        int currLength = 1;
        int maxLength = 1;
        char[] chars = s.toCharArray( );
        Set<Character> charSet = new HashSet<>( );
        // dvdf
        for (int i = 0; i < chars.length - 1; i++) {
            if (maxLength > chars.length - i) {
                break;
            }
            if (chars[i] == chars[i + 1]) {
                continue;
            }
            charSet.add(chars[i]);
            for (int j = i + 1; j < chars.length; j++) {
                if (charSet.add(chars[j])) {
                    currLength++;
                } else {
                    if (currLength > maxLength) {
                        maxLength = currLength;
                    }
                    currLength = 1;
                    charSet = new HashSet<>( );
                    break;
                }
            }
        }
        return maxLength > currLength ? maxLength : currLength;
    }

    /**
     * 比如:
     * galdfldfghlad
     * 将字符串截断，截断的标准是重复字符
     * 从(g,0)开始 flag = 0
     * galdf
     * l重复,从(l,2)开始继续匹配，起始长度[df]:2, index[5] - pos[2] - 1 = 3
     * ldfl
     * d重复,从(d,3)开始继续，起始长度：2，index[]
     * fld
     * f重复,从(f,4)继续
     * ldfgh
     * l重复，从(l,5)继续【此时是第二个l了】
     * dfghla
     * d重复，(d,6)继续
     * fghlad
     * 结束
     * <p>
     * pwwkew
     * pw
     * w 重复（w,1）
     */
    public int lengthOfLongestSubstringV2(String s) {
        if (null == s || "".equals(s)) {
            return 0;
        }
        int flag = 0;
        int currLength = 0;
        int maxLength = 0;
        int index = 0;
        while (index < s.length( )) {
            int pos = s.indexOf(s.charAt(index), flag);
            if (pos < index) {
                // 前面有重复的字符了
                //当前子串的长度
                if (currLength > maxLength) {
                    maxLength = currLength;
                }
                // 起始长度有问题
                currLength = index - pos - 1;
                flag = pos + 1;
            }
            index++;
            currLength++;
        }
        return maxLength > currLength ? maxLength : currLength;
    }

    public static void main(String[] args) {
        LongestSubstring substring = new LongestSubstring( );
        int length;
        length = substring.lengthOfLongestSubstringV2("pwwkew");
        System.out.println("length 3 = " + length);
        length = substring.lengthOfLongestSubstringV2("bbbbb");
        System.out.println("length 1 = " + length);
        length = substring.lengthOfLongestSubstringV2("aab");
        System.out.println("length 2 = " + length);
        length = substring.lengthOfLongestSubstringV2("pwwkew");
        System.out.println("length 3 = " + length);
    }
}
